#include <stdio.h>

#include "string.h"

// 返回子串t在主串s中第一次出现的位置，若不存在，则返回-1
int Index(SqString s, SqString t) {
    int i, j, k;
    for (i = 0; i <= s.length - t.length; i++) {
        for (k = i, j = 0; k < s.length && j < t.length && s.data[k] == t.data[j]; k++, j++);
        if (j == t.length)
            return i;
    }
    return -1;
}

void GetNext(SqString t, int next[]) {
    int j, k;
    j = 0; k = -1; next[0] = -1;  // 第一个字符的最大公共前后缀长度为0
    while (j < t.length - 1) {
        if (k == -1 || t.data[j] == t.data[k]) {
            j++; k++;
            next[j] = k;
        } else {
            k = next[k];  // 回退到next[k]位置
        }
    }
}

int KMPIndex(SqString s, SqString t) {
    int next[MAXSIZE], i = 0, j = 0;
    GetNext(t, next);
    while (i < s.length && j < t.length) {
        if (j == -1 || s.data[i] == t.data[j]) {
            i++; j++;
        } else {
            j = next[j];
    }
    if(j >= t.length)
        return i - t.length;
    else return -1;
}

void TestPatternMatching(char s1[], char s2[]) {
    printf("test begin\n");

    struct {
        char name[20];
        int (*pm)(SqString, SqString);
    } testFunc[] = {
        {"BF算法", Index},
        {"KMP算法", KMPIndex},
    };

    SqString s, t;
    StrAssign(&s, s1);
    printf("%s\n", s.data);
    StrAssign(&t, s2);
    printf("%s\n", t.data);

    for (int i = 0; i < sizeof(testFunc) / sizeof(testFunc[0]); ++i) {
        printf("%s: %d\n", testFunc[i].name, testFunc[i].pm(s, t));
    }

    printf("test end\n");
    printf("——————————————————————————————————\n");
}

int main() {
    char s0[] = "hello world";
    char t0[] = "he";
    TestPatternMatching(s0, t0);

    char s1[] = "hello world";
    char t1[] = "ld";
    TestPatternMatching(s1, t1);

    char s2[] = "hello world";
    char t2[] = "world";
    TestPatternMatching(s2, t2);

    char s3[] = "hello world";
    char t3[] = "world!";
    TestPatternMatching(s3, t3);

    char s4[] = "aaaaa";
    char t4[] = "aaa";
    TestPatternMatching(s4, t4);

    char s5[] = "CAAGAAAUAUAUACCUCACU";
    char t5[] = "AUAUAC";
    TestPatternMatching(s5, t5);

    char s6[] = "ACAATACAAT";
    char t6[] = "ACAAT";
    TestPatternMatching(s6, t6);

    return 0;
}